package my.study.java.basic.algorithm.sorts;

import java.util.Random;

/**
 * 
 * 选择排序和冒泡排序有一些相似之处，要对具有n个元素的序列进行n - 1趟扫描，
 * 每趟扫描中，从为排序的部分中挑选出最大的元素，放在正确的位置，
 * 此算法比冒泡算法的效率高一些，因为从为排序部分中挑选出最大元素的过程，算法不移动任何元素。
 * 只有在找到最大元素后才进行一次元素交换操作
 * T(n) = O(n^2) 
 * 
 * @author fanongjie
 */
public class SelectSort {
	private static final int N = 9;
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Element array[] = new Element[N];
		Random random = new Random();
		for (int i = 0; i < N; i++) {
			array[i] = new Element(random.nextInt(2 * N)); 
		}
		System.out.print("Init:\t");
		for (int i = 0; i < N; i++) {
			System.out.print(array[i].getValue() + "\t");
		}
		System.out.println();
		//Select Sort()
		for (int i = 0; i < N - 1; i++) {
			int max = i;
			for (int j = i + 1; j < N; j++) {				
				if (array[max].compareTo(array[j]) > 0) {
					max = j;
				}
			}
			Element o = array[i];
			array[i] = array[max];
			array[max] = o;
			System.out.print((i + 1) + ":\t");
			for (int k = 0; k < N; k++) {
				System.out.print(array[k].getValue() + "\t");
			}
			System.out.println();
		}
		
		System.out.print("Result:\t");
		for (int i = 0; i < N; i++) {
			System.out.print(array[i].getValue() + "\t");
		}
		System.out.println();
	}

}
